/**
 *  File: httpd.c
 *
 *  Copyright (C) 2008 Du XiaoGang <dugang@188.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 */

#include "common.h"

#define LISTEN_BACKLOG  1024
#define REQ_MAX         4096
#define URL_MAX         1024
#define BLOCK_MAX       0x100000    /* 1Mbytes */

/* States for checked_state(from thttpd/2.25b). */
#define CHST_FIRSTWORD  0
#define CHST_FIRSTWS    1
#define CHST_SECONDWORD 2
#define CHST_SECONDWS   3
#define CHST_THIRDWORD  4
#define CHST_THIRDWS    5
#define CHST_LINE       6
#define CHST_LF         7
#define CHST_CR         8                
#define CHST_CRLF       9
#define CHST_CRLFCR     10
#define CHST_BOGUS      11

#define GR_NO_REQUEST   0
#define GR_GOT_REQUEST  1
#define GR_BAD_REQUEST  2

struct connection_t {
    int fd;
    /* request */
    char req_buf[REQ_MAX];
    size_t req_read;
    size_t req_checked;
    int checked_state;
#define METHOD_HEAD     0
#define METHOD_GET      1
    int method;
    /* response */
    struct entity_t *entity;
    int entity_dyn;
    size_t header_sent;
    size_t body_sent;
};

extern struct entity_t *make_statpage(void);
extern void get_cpustat(pid_t pid, int *id, int *pu, int *ps, struct timeval *tv);
extern void get_memusage(pid_t pid, double *total, double *used, double *cached, 
                         double *process);
extern struct entity_t *make_chartjar(void);
extern int get_cpucount(void);

/* for statistic */
extern time_t stat_begin_time;
extern int begin_idx, stat_count, ncpu;
extern struct statistic_t stat_arr[STAT_COUNT_MAX];
extern double mem_total;  /* in mbytes */

static void show_help(void);
static void error_init(void);
static void error_install(int status, const char *text);
static int error_cmp(const void *a, const void *b);
static void entity_init(const char *path);
static void _get_file_list(const char *path);
static int entity_cmp(const void *a, const void *b);
static struct entity_t *entity_get(const char *path);
static int listen_init(void);
static int set_noblock(int fd);
static int got_request(struct connection_t *hc);
static void send_error(struct connection_t *c, int status);
static void clear_connection(struct connection_t *c);
static int parse_request(struct connection_t *c);
static void url_decode(char *to, char *from);
static int hexit(char c);
static void de_dotdot(char *file);
static struct entity_t *make_blockdata(int size);

static struct entity_t *entity_arr = NULL;
static size_t entity_count, entity_alloced;
static int ignore_len;
static struct entity_t *error_arr = NULL;
static size_t error_count, error_alloced;
static int conns_limit = 1000, cur_conns = 0;
static char *root_dir = "/var/www/html";
static int listen_port = 80;

int
main(int argc, char *argv[])
{
#define UPDATE_IDX \
        do { \
            if (last_idx == -1) { \
                /* first stat */ \
                stat_begin_time = time(NULL); \
                duration = 0; \
                idx = 0; \
            } else { \
                duration = time(NULL) - stat_begin_time; \
                idx = duration / STAT_INTERVAL % STAT_COUNT_MAX; \
            } \
            if (last_idx != idx) { \
                int tmp_id, tmp_pu, tmp_ps, lasttime; \
                struct timeval tmp_tv; \
                memset(&stat_arr[idx], 0, sizeof(struct statistic_t)); \
                last_idx = idx; \
                /* begin_idx */ \
                if (duration / STAT_INTERVAL >= STAT_COUNT_MAX) { \
                    begin_idx++; \
                    if (begin_idx == STAT_COUNT_MAX) \
                        begin_idx = 0; \
                } \
                /* get cpu usage */ \
                get_cpustat(pid, &tmp_id, &tmp_pu, &tmp_ps, &tmp_tv); \
                lasttime = (tmp_tv.tv_sec - btv.tv_sec) * 1000000 + (tmp_tv.tv_usec - btv.tv_usec); \
                stat_arr[idx].cpu_usedp = 100 - (tmp_id - idle_tick) * 1000000 / HZ / ncpu * 100 / lasttime; \
                stat_arr[idx].cpu_httpdp = (tmp_pu + tmp_ps - pu_tick - ps_tick) * 1000000 / HZ / ncpu * 100 / lasttime; \
                idle_tick = tmp_id; \
                pu_tick = tmp_pu; \
                ps_tick = tmp_ps; \
                btv = tmp_tv; \
                /* get memory usage */ \
                get_memusage(pid, &mem_total, &mem_used, &mem_cached, &mem_process); \
                stat_arr[idx].mem_usedp = (int)(mem_used / mem_total * 100 + 0.5); \
                stat_arr[idx].mem_cachedp = (int)(mem_cached / mem_total * 100 + 0.5); \
                stat_arr[idx].mem_httpdp = (int)(mem_process / mem_total * 100 + 0.5); \
                stat_count++; \
            } \
        } while (0)

    int ret, max_fd, listenfd, epollfd, nfd, i, cur_fd, conn_fd, idx, last_idx = -1;
    struct rlimit rlmt;
    struct epoll_event epollevt, *outevtarr;
    struct connection_t *conn;
    time_t duration;
    pid_t pid;
    int idle_tick, pu_tick, ps_tick;
    struct timeval btv;
    double mem_used, mem_cached, mem_process;

    /* parse arguments line */
    while (1) {
        ret = getopt(argc, argv, "c:d:p:");
        if (ret == -1) {
            if (argv[optind] != NULL) {
                show_help();
                exit(1);
            }
            break;
        }
        switch (ret) {
        case 'c':
            conns_limit = atoi(optarg);
            if (conns_limit < 1 || conns_limit > 10000) {
                fprintf(stderr, "The max connection number should be in [1, 10000].");
                exit(1);
            }
            break;
        case 'd':
            if (optarg[0] != '/') {
                fprintf(stderr, "The www root directory should be absolute path.");
                exit(1);
            }
            root_dir = strdup(optarg);
            if (root_dir == NULL)
                ERR("null");
            break;
        case 'p':
            listen_port = atoi(optarg);
            if (listen_port < 1 || listen_port > 65536) {
                fprintf(stderr, "The listen port should be in [1, 65536].");
                exit(1);
            }
            break;
        default:
            show_help();
            exit(1);
        }
    }

    /* set max fd */
    max_fd = conns_limit + 10;
    ret = getrlimit(RLIMIT_NOFILE, &rlmt);
    if (ret == -1) {
        ERR("null");
        exit(1);
    }
    if (max_fd > rlmt.rlim_cur) {
        rlmt.rlim_cur = max_fd;
        rlmt.rlim_max = max_fd;
        ret = setrlimit(RLIMIT_NOFILE, &rlmt);
        if (ret == -1) {
            if (errno == EPERM)
                fprintf(stderr, "Failed to change resource limit, operation disallowed.\n");
            else
                ERR("null");
            exit(1);
        }
    }

    /* signal */
    signal(SIGPIPE, SIG_IGN);

    /* initialize error cache */
    error_init();

    /* initialize entity cache */
    entity_init(root_dir);

    /* init listen socket */
    listenfd = listen_init();

    /* init epoll */
    epollfd = epoll_create(max_fd);
    if (epollfd == -1) { 
        ERR("null");
        exit(1);
    }

    /* alloc outevtarr */
    outevtarr = malloc(max_fd * sizeof(struct epoll_event));
    if (outevtarr == NULL) {
        ERR("null");
        exit(1);
    }

    /* add listenfd to epoll array */
    memset(&epollevt, 0, sizeof(epollevt));
    epollevt.events = EPOLLIN;
    epollevt.data.fd = listenfd;
    ret = epoll_ctl(epollfd, EPOLL_CTL_ADD, listenfd, &epollevt);
    if (ret == -1) {
        ERR("null");
        exit(1);
    }

    /* get current pid */
    pid = getpid();
    /* get cpu count */
    ncpu = get_cpucount();
    if (ncpu == -1) {
        /* error */
        exit(1);
    }
    /* cpu stat */
    get_cpustat(pid, &idle_tick, &pu_tick, &ps_tick, &btv);
    /* get total memory */
    get_memusage(pid, &mem_total, &mem_used, &mem_cached, &mem_process);

    /* main loop */
    while (1) {
        nfd = epoll_wait(epollfd, outevtarr, max_fd, 600);
        if (nfd == -1) {
            if (errno == EINTR)
                continue;
            /* other error */
            ERR("null");
            exit(1);
        } else if (nfd == 0) {
            /* timeout */
            UPDATE_IDX;
            continue;
        }

        /* have some events */
        for (i = 0; i < nfd; i++) {
            cur_fd = outevtarr[i].data.fd;

            /* for listenfd */
            if (cur_fd == listenfd) {
                if (outevtarr[i].events & EPOLLIN) {
                    /* new requests arrived */
                    while (1) {
                        if (cur_conns == conns_limit) {
                            /* reach connections limit, ignore */
                            break;
                        }

                        /* accept */
                        conn_fd = accept(listenfd, NULL, NULL);
                        if (conn_fd == -1) {
                            /* accept error, ignore request */
                            if (errno != EAGAIN)
                                ERR("null");
                            /* dont call accept again */
                            break;
                        }

                        /* accepted */
                        UPDATE_IDX;
                        stat_arr[idx].accepted++;
                        
                        /* no-blocking */
                        ret = set_noblock(conn_fd);
                        if (ret == -1) {
                            ERR("null");
                            /* ignore and next */
                            close(conn_fd);
                            continue;
                        }

                        /* new connection_t */
                        conn = malloc(sizeof(struct connection_t));
                        if (conn == NULL) {
                            ERR("null");
                            /* ignore and next */
                            close(conn_fd);
                            continue;
                        }
                        conn->fd = conn_fd;
                        conn->req_read = 0;
                        conn->req_checked = 0;
                        conn->checked_state = CHST_FIRSTWORD;
                        conn->entity = NULL;
                        conn->entity_dyn = 0;
                        conn->header_sent = 0;
                        conn->body_sent = 0;

                        /* add conn_fd to epoll array */
                        memset(&epollevt, 0, sizeof(epollevt));
                        epollevt.events = EPOLLIN;
                        epollevt.data.u64 = ((unsigned long long)(unsigned int)conn << 32)
                                            | conn_fd;
                        ret = epoll_ctl(epollfd, EPOLL_CTL_ADD, conn_fd, &epollevt);
                        if (ret == -1) {
                            ERR("null");
                            exit(1);
                        }
    
                        /* update cur_conns */
                        cur_conns++;
                        if (cur_conns > stat_arr[idx].max_conns)
                            stat_arr[idx].max_conns = cur_conns;
                    }
                } else {
                    /* error */
                    ERR("null");
                    exit(1);
                }
            } else {
                /* connection */
                conn = (struct connection_t *)((unsigned int)(outevtarr[i].data.u64 >> 32));

                if (outevtarr[i].events & EPOLLIN) {
                    /* read request */
                    while (1) {
                        if (conn->req_read == sizeof(conn->req_buf) - 1) {
                            /* Request Entity Too Large */
                            send_error(conn, 413);
                            /* change to write mode */
                            memset(&epollevt, 0, sizeof(epollevt));
                            epollevt.events = EPOLLOUT;
                            epollevt.data.u64 = outevtarr[i].data.u64;
                            ret = epoll_ctl(epollfd, EPOLL_CTL_MOD, cur_fd, &epollevt);
                            if (ret == -1) {
                                ERR("null");
                                exit(1);
                            }
                            break;
                        }

                        /* read */
                        ret = read(cur_fd, conn->req_buf + conn->req_read, 
                                   sizeof(conn->req_buf) - 1 - conn->req_read);
                        if (ret == -1) {
                            if (errno == EAGAIN) {
                                break;
                            } else {
                                /* error, clear connection */
                                ERR("null");
                                clear_connection(conn);
                                break;
                            }
                        } else if (ret == 0) {
                            /* Bad Request */
                            send_error(conn, 400);
                            /* change to write mode */
                            memset(&epollevt, 0, sizeof(epollevt));
                            epollevt.events = EPOLLOUT;
                            epollevt.data.u64 = outevtarr[i].data.u64;
                            ret = epoll_ctl(epollfd, EPOLL_CTL_MOD, cur_fd, &epollevt);
                            if (ret == -1) {
                                ERR("null");
                                exit(1);
                            }
                            break;
                        } else {
                            /* read some data */
                            conn->req_read += ret;
                            conn->req_buf[conn->req_read] = '\0';

                            /* received */
                            UPDATE_IDX;
                            stat_arr[idx].received += ret;

                            /* got request header? */
                            ret = got_request(conn);
                            if (ret == GR_NO_REQUEST) {
                                continue;
                            } else if (ret == GR_BAD_REQUEST) {
                                /* Bad Request */
                                send_error(conn, 400);
                                /* change to write mode */
                                memset(&epollevt, 0, sizeof(epollevt));
                                epollevt.events = EPOLLOUT;
                                epollevt.data.u64 = outevtarr[i].data.u64;
                                ret = epoll_ctl(epollfd, EPOLL_CTL_MOD, cur_fd, &epollevt);
                                if (ret == -1) {
                                    ERR("null");
                                    exit(1);
                                }
                                break;
                            }

                            /* GR_GOT_REQUEST, parse it */
                            parse_request(conn);
                            /* change to write mode */
                            memset(&epollevt, 0, sizeof(epollevt));
                            epollevt.events = EPOLLOUT;
                            epollevt.data.u64 = outevtarr[i].data.u64;
                            ret = epoll_ctl(epollfd, EPOLL_CTL_MOD, cur_fd, &epollevt);
                            if (ret == -1) {
                                ERR("null");
                                exit(1);
                            }
                            break;
                        }
                    }
                } else if (outevtarr[i].events & EPOLLOUT) {
                    /* send response */
                    /* for header */
                    while (conn->header_sent < conn->entity->header_length) {
                        ret = write(cur_fd, conn->entity->header + conn->header_sent, 
                                    conn->entity->header_length - conn->header_sent);
                        if (ret < 0) {
                            if (errno == EAGAIN)
                                goto for_next;
                            /* error */
                            ERR("null");
                            goto failed;
                        }
                        /* send some data */
                        conn->header_sent += ret;

                        /* sent */
                        UPDATE_IDX;
                        stat_arr[idx].sent += ret;
                    }

                    /* for body */
                    if (conn->method == METHOD_GET) {
                        while (conn->body_sent < conn->entity->body_length) {
                            ret = write(cur_fd, conn->entity->body + conn->body_sent, 
                                        conn->entity->body_length - conn->body_sent);
                            if (ret < 0) {
                                if (errno == EAGAIN)
                                    goto for_next;
                                /* error */
                                ERR("null");
                                goto failed;
                            }
                            /* send some data */
                            conn->body_sent += ret;

                            /* sent */
                            UPDATE_IDX;
                            stat_arr[idx].sent += ret;
                        }
                    }

                    /* all sent */
                    shutdown(conn->fd, SHUT_WR);

                    /* completed */
                    UPDATE_IDX;
                    stat_arr[idx].completed++;
failed:
                    clear_connection(conn);
for_next:
                    continue;
                } else {
                    /* error, clear connection */
                    ERR("null");
                    clear_connection(conn);
                }
            }
        }
    }

    return 0;
}

static void 
show_help(void)
{
    printf("usage: testhttpd [-c(%d): max connection number]\n"
           "                 [-d(%s): www root directory]\n"
           "                 [-p(%d): listen port]\n",
           conns_limit, root_dir, listen_port);
}

static void
error_init(void)
{
#define ERROR_ALLOC_STEP    16
    error_count = 0;
    error_alloced = ERROR_ALLOC_STEP;
    error_arr = malloc(sizeof(struct entity_t) * error_alloced);
    if (error_arr == NULL) {
        ERR("null");
        exit(1);
    }

    /* install */
    error_install(304, "Not Modified");
    error_install(400, "Bad Request");
    error_install(404, "Not Found");
    error_install(413, "Request Entity Too Large");
    error_install(414, "Request-URI Too Long");
    error_install(500, "Internal Server Error");
    error_install(501, "Not Implemented");
    
    qsort(error_arr, error_count, sizeof(struct entity_t), error_cmp);
}

static void
error_install(int status, const char *text)
{
    int ret;
    char header[4096];

    if (error_count == error_alloced) {
        error_alloced += ERROR_ALLOC_STEP;
        error_arr = realloc(error_arr, sizeof(struct entity_t) * error_alloced);
        if (error_arr == NULL) {
            ERR("null");
            exit(1);
        }
    }

    /* status */
    error_arr[error_count].u.status = status;

    /* header */
    ret = snprintf(header, sizeof(header), 
                   "HTTP/1.1 %d %s\r\n"
                   "Server: %s/%s\r\n"
                   "Content-Length: 0\r\n"
                   "Accept-Ranges: none\r\n"
                   "Connection: close\r\n"
                   "\r\n", 
                   status, text, SOFTWARE, VERSION);
    if (ret >= sizeof(header)) {
        ERR("null");
        exit(1);
    }
    error_arr[error_count].header_dyn = 0;
    error_arr[error_count].header_length = ret;
    error_arr[error_count].header = strdup(header);
    if (error_arr[error_count].header == NULL) {
        ERR("null");
        exit(1);
    }

    /* body */
    error_arr[error_count].body_dyn = 0;
    error_arr[error_count].body_length = 0;
    error_arr[error_count].body = NULL;

    error_count++;
}

static int
error_cmp(const void *a, const void *b)
{
    struct entity_t *ea, *eb;

    ea = (struct entity_t*)a;
    eb = (struct entity_t*)b;
    return (ea->u.status - eb->u.status);
}

static void
entity_init(const char *path)
{
#define ENTITY_ALLOC_STEP   16
    ignore_len = strlen(path);
    if (path[ignore_len - 1] != '/')
        ignore_len++;

    entity_count = 0;
    entity_alloced = ENTITY_ALLOC_STEP;
    entity_arr = malloc(sizeof(struct entity_t) * entity_alloced);
    if (entity_arr == NULL) {
        ERR("null");
        exit(1);
    }

    _get_file_list(path);
    
    qsort(entity_arr, entity_count, sizeof(struct entity_t), entity_cmp);
}

static void 
_get_file_list(const char *path)
{
    DIR *dir;
    struct dirent *entry;
    int len, ret, fd;
    char file[PATH_MAX], header[4096];
    struct stat st;

    dir = opendir(path);
    if (dir == NULL) {
        fprintf(stderr, "Failed to open directory(%s), errno = %d.\n", path, errno);
        exit(1);
    }

    len = strlen(path);
    /* for each file */
    while (1) {
        entry = readdir(dir);
        if (entry == NULL)
            break;

        /* ignore ./.. */
        if (strcmp(entry->d_name, ".") == 0
            || strcmp(entry->d_name, "..") == 0 )
        {
            continue;
        }

        if (path[len - 1] == '/')
            snprintf(file, PATH_MAX, "%s%s", path, entry->d_name);
        else
            snprintf(file, PATH_MAX, "%s/%s", path, entry->d_name);
        
        /* get more info */
        ret = stat(file, &st);
        if (ret == -1) {
            fprintf(stderr, "Failed to stat file(%s), errno = %d.\n", file, errno);
            exit(1);
        }

        if (S_ISDIR(st.st_mode)) {
            /* dir */
            _get_file_list(file);
        } else if (S_ISREG(st.st_mode)) {
            /* normal file, including target of symbol link */
            if (entity_count == entity_alloced) {
                entity_alloced += ENTITY_ALLOC_STEP;
                entity_arr = realloc(entity_arr, sizeof(struct entity_t) * entity_alloced);
                if (entity_arr == NULL) {
                    ERR("null");
                    exit(1);
                }
            }

            /* name */
            entity_arr[entity_count].u.name = strdup(&file[ignore_len]);
            if (entity_arr[entity_count].u.name == NULL) {
                ERR("null");
                exit(1);
            }

            /* header */
            ret = snprintf(header, sizeof(header), 
                           "HTTP/1.1 200 OK\r\n"
                           "Server: %s/%s\r\n"
                           "Content-Length: %d\r\n"
                           "Accept-Ranges: none\r\n"
                           "Connection: close\r\n"
                           "\r\n", 
                           SOFTWARE, VERSION, (int)st.st_size);
            if (ret >= sizeof(header)) {
                ERR("null");
                exit(1);
            }
            entity_arr[entity_count].header_dyn = 0;
            entity_arr[entity_count].header_length = ret;
            entity_arr[entity_count].header = strdup(header);
            if (entity_arr[entity_count].header == NULL) {
                ERR("null");
                exit(1);
            }

            /* body */
            entity_arr[entity_count].body_dyn = 0;
            entity_arr[entity_count].body_length = st.st_size;
            entity_arr[entity_count].body = malloc(st.st_size);
            if (entity_arr[entity_count].body == NULL) {
                ERR("null");
                exit(1);
            }
            fd = open(file, O_RDONLY);
            if (fd == -1) {
                fprintf(stderr, "Failed to open file(%s), errno = %d.\n", file, errno);
                exit(1);
            }
            ret = read(fd, (void *)entity_arr[entity_count].body, st.st_size);
            if (ret != st.st_size) {
                ERR("null");
                exit(1);
            }
            close(fd);

            entity_count++;
        }
    }
    closedir(dir);
}

static int
entity_cmp(const void *a, const void *b)
{
    struct entity_t *ea, *eb;

    ea = (struct entity_t*)a;
    eb = (struct entity_t*)b;
    return strcmp(ea->u.name, eb->u.name);
}

static struct entity_t *
entity_get(const char *path)
{
    struct entity_t s, *rets;
    
    s.u.name = (char*)path;
    rets = (struct entity_t*)bsearch(&s, entity_arr, entity_count, 
                                     sizeof(struct entity_t), entity_cmp);
    return rets;
}

static int
listen_init(void)
{
    int listenfd, ret, on;
    struct sockaddr_in localaddr;

    /* init listen port */
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1) {
        ERR("null");
        exit(1);
    }

    /* set noblock */
    ret = set_noblock(listenfd);
    if (ret == -1) {
        ERR("null");
        exit(1);
    }

    /* SO_REUSEADDR */
    on = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, (const void *)&on, sizeof(on));

    /* bind */
    localaddr.sin_family = AF_INET;
    localaddr.sin_addr.s_addr = inet_addr("0.0.0.0");
    localaddr.sin_port = htons(listen_port);
    ret = bind(listenfd, (struct sockaddr *)&localaddr, sizeof(localaddr));
    if (ret == -1) {
        fprintf(stderr, 
                "Failed to bind listen socket on (0.0.0.0:%d), errno = %d.\n",
                listen_port, errno);
        exit(1);
    }

    /* listen */
    ret = listen(listenfd, LISTEN_BACKLOG);
    if (ret == -1) {
        ERR("null");
        exit(1);
    }

    return listenfd;
}

static int 
set_noblock(int fd)
{
    int flag, ret;

    flag = fcntl(fd, F_GETFL);
    if (flag == -1)
        return -1;
    ret = fcntl(fd, F_SETFL, flag | O_NONBLOCK);
    if (ret == -1)
        return -1;
    return 0;
}

/* from thttpd/2.25b. */
static int
got_request(struct connection_t *conn)
{
    char c;

    for (; conn->req_checked < conn->req_read; ++conn->req_checked) {
        c = conn->req_buf[conn->req_checked];
        switch (conn->checked_state) {
        case CHST_FIRSTWORD:
            switch (c) {
            case ' ':
            case '\t': 
                conn->checked_state = CHST_FIRSTWS;
                break;
            case '\n':
            case '\r': 
                conn->checked_state = CHST_BOGUS;
                return GR_BAD_REQUEST;
            }
            break;
        case CHST_FIRSTWS:
            switch (c) {
            case ' ':
            case '\t':
                break;
            case '\n':
            case '\r':
                conn->checked_state = CHST_BOGUS;
                return GR_BAD_REQUEST;
            default:
                conn->checked_state = CHST_SECONDWORD;
                break;
            }
            break;
        case CHST_SECONDWORD:
            switch (c) {
            case ' ':
            case '\t':
                conn->checked_state = CHST_SECONDWS;
                break;
            case '\n':
            case '\r':
                conn->checked_state = CHST_BOGUS;
                return GR_BAD_REQUEST;
            }
            break;
        case CHST_SECONDWS:
            switch (c) {
            case ' ':
            case '\t':
                break;
            case '\n':
            case '\r':
                conn->checked_state = CHST_BOGUS;
                return GR_BAD_REQUEST;
            default:
                conn->checked_state = CHST_THIRDWORD;
                break;
            }
            break;
        case CHST_THIRDWORD:
            switch (c) {
            case ' ':
            case '\t':
                conn->checked_state = CHST_THIRDWS;
                break;
            case '\n':
                conn->checked_state = CHST_LF;
                break;
            case '\r':
                conn->checked_state = CHST_CR;
                break;
            }
            break;
        case CHST_THIRDWS:
            switch (c) {
            case ' ':
            case '\t':
                break;
            case '\n':
                conn->checked_state = CHST_LF;
                break;
            case '\r':
                conn->checked_state = CHST_CR;
                break;
            default:
                conn->checked_state = CHST_BOGUS;
                return GR_BAD_REQUEST;
            }
            break;
        case CHST_LINE:
            switch (c) {
            case '\n':
                conn->checked_state = CHST_LF;
                break;
            case '\r':
                conn->checked_state = CHST_CR;
                break;
            }
            break;
        case CHST_LF:
            switch (c) {
            case '\n':
                /* Two newlines in a row - a blank line - end of request. */
                return GR_GOT_REQUEST;
            case '\r':
                conn->checked_state = CHST_CR;
                break;
            default:
                conn->checked_state = CHST_LINE;
                break;
            }
            break;
        case CHST_CR:
            switch (c) {
            case '\n':
                conn->checked_state = CHST_CRLF;
                break;
            case '\r':
                /* Two returns in a row - end of request. */
                return GR_GOT_REQUEST;
            default:
                conn->checked_state = CHST_LINE;
                break;
            }
            break;
        case CHST_CRLF:
            switch (c) {
            case '\n':
                /* Two newlines in a row - end of request. */
                return GR_GOT_REQUEST;
            case '\r':
                conn->checked_state = CHST_CRLFCR;
                break;
            default:
                conn->checked_state = CHST_LINE;
                break;
            }
            break;
        case CHST_CRLFCR:
            switch (c) {
            case '\n':
            case '\r':
                /* Two CRLFs or two CRs in a row - end of request. */
                return GR_GOT_REQUEST;
            default:
                conn->checked_state = CHST_LINE;
                break;
            }
            break;
        case CHST_BOGUS:
            return GR_BAD_REQUEST;
        }
    }
    return GR_NO_REQUEST;
}

static void 
send_error(struct connection_t *c, int status)
{
    struct entity_t s, *rets;
    
    s.u.status = status;
    rets = (struct entity_t*)bsearch(&s, error_arr, error_count, 
                                     sizeof(struct entity_t), error_cmp);
    if (rets == NULL) {
        ERR("null");
        exit(1);
    }
    c->entity = rets;
}

static void
clear_connection(struct connection_t *c)
{
    close(c->fd);
    if (c->entity_dyn) {
        if (c->entity->header_dyn)
            free(c->entity->header);
        if (c->entity->body_dyn)
            free(c->entity->body);
        free(c->entity);
    }
    free(c);
    cur_conns--;
}

static int 
parse_request(struct connection_t *c)
{
    char *p, *q, *rest, url[URL_MAX];
    int size;

    p = c->req_buf;
    /* get http method */
    p += strspn(p, " \t");
    q = strpbrk(p, " \t");
    if (q == NULL) {
        /* Bad Request */
        send_error(c, 400);
        return -1;
    }
    if (q - p == 4 && p[0] == 'H' && p[1] == 'E' && p[2] == 'A' && p[3] == 'D') {
        /* HEAD */
        c->method = METHOD_HEAD;
    } else if (q - p == 3 && p[0] == 'G' && p[1] == 'E' && p[2] == 'T') {
        /* GET */
        c->method = METHOD_GET;
    } else {
        /* Not Implemented */
        send_error(c, 501);
        return -1;
    }

    /* get dest url */
    p = q;
    p += strspn(p, " \t");
    q = strpbrk(p, " \t");
    if (q == NULL) {
        /* Bad Request */
        send_error(c, 400);
        return -1;
    }
    *q = '\0';
    rest = q + 1;

    /* check url length */
    if (q - p >= URL_MAX) {
        /* Request-URI Too Long */
        send_error(c, 414);
        return -1;
    }

    /* absolute url? */
    if (*p != '/') {
        /* Bad Request */
        send_error(c, 400);
        return -1;
    }

    /* remove query part */
    q = strchr(p, '?');
    if (q != NULL)
        *q = '\0';

    /* url decode */
    url_decode(p, p);

    /* remove leading '/' */
    strcpy(url, p + 1);
    if (url[0] == '\0')
        strcpy(url, "index.html");

    /* for security */
    de_dotdot(url);
    if (url[0] == '/'
        || (url[0] == '.' && url[1] == '.' && (url[2] == '\0' || url[2] == '/')))
    {
        /* Bad Request */
        send_error(c, 400);
        return -1;
    }

    //printf("request url: %s\n", url);
    /* request memory block or stat page? */
    if (strncmp(url, "local/block/", 12) == 0) {
        size = atoi(url + 12);
        if (size <= 0 || size > BLOCK_MAX) {
            send_error(c, 400);
            return -1;
        }
        c->entity = make_blockdata(size);
        if (c->entity == NULL) {
            send_error(c, 500);
            return -1;
        } else {
            /* need free */
            c->entity_dyn = 1;
            return 0;
        }
    } else if (strcmp(url, "local/stat") == 0) {
        c->entity = make_statpage();
        if (c->entity == NULL) {
            send_error(c, 500);
            return -1;
        } else {
            /* need free */
            c->entity_dyn = 1;
            return 0;
        }
    } else if (strcmp(url, "local/chart.jar") == 0) {
        /* conditional GET? */
        if (strcasestr(rest, "If-Modified-Since") != NULL) {
            send_error(c, 304);
            return -1;
        } else {
            c->entity = make_chartjar();
            if (c->entity == NULL) {
                send_error(c, 500);
                return -1;
            } else {
                /* need free */
                c->entity_dyn = 1;
                return 0;
            }
        }
    }

    c->entity = entity_get(url);
    if (c->entity == NULL) {
        /* Not Found */
        send_error(c, 404);
        return -1;
    }

    return 0;
}

/* Copies and decodes a string.  It's ok for from and to to be the
** same string.
*/
static void
url_decode(char *to, char *from)
{
    for (; *from != '\0'; ++to, ++from) {
        if (from[0] == '%' && isxdigit(from[1]) && isxdigit(from[2])) {
            *to = hexit(from[1]) * 16 + hexit(from[2]);
            from += 2;
        } else {
            *to = *from;
        }
    }
    *to = '\0';
}

static int
hexit(char c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    if (c >= 'a' && c <= 'f')
        return c - 'a' + 10;
    if (c >= 'A' && c <= 'F')
        return c - 'A' + 10;
    return 0;           /* shouldn't happen, we're guarded by isxdigit() */
}

static void
de_dotdot(char *file)
{
    char *cp;
    char *cp2;
    int l;

    /* Collapse any multiple / sequences. */
    while ((cp = strstr(file, "//")) != (char *) 0) {
        for (cp2 = cp + 2; *cp2 == '/'; ++cp2)
            continue;
        (void) strcpy(cp + 1, cp2);
    }

    /* Remove leading ./ and any /./ sequences. */
    while (strncmp(file, "./", 2) == 0)
        (void) strcpy(file, file + 2);
    while ((cp = strstr(file, "/./")) != (char *) 0)
        (void) strcpy(cp, cp + 2);

    /* Alternate between removing leading ../ and removing xxx/../ */
    for (;;) {
        while (strncmp(file, "../", 3) == 0)
            (void) strcpy(file, file + 3);
        cp = strstr(file, "/../");
        if (cp == (char *) 0)
            break;
        for (cp2 = cp - 1; cp2 >= file && *cp2 != '/'; --cp2)
            continue;
        (void) strcpy(cp2 + 1, cp + 4);
    }

    /* Also elide any xxx/.. at the end. */
    while ((l = strlen(file)) > 3 && strcmp((cp = file + l - 3), "/..") == 0) {
        for (cp2 = cp - 1; cp2 >= file && *cp2 != '/'; --cp2)
            continue;
        if (cp2 < file)
            break;
        *cp2 = '\0';
    }
}

static struct entity_t *
make_blockdata(int size)
{
    struct entity_t *rets;
    static int block_inited = 0;
    static char block_buf[BLOCK_MAX];

    if (!block_inited) {
        memset(block_buf, '.', sizeof(block_buf));
        snprintf(block_buf, sizeof(block_buf), 
                 "HTTP/1.1 200 OK\r\n"
                 "Server: %s/%s\r\n"
                 "Content-Type: text/html; charset=utf-8\r\n"
                 "Cache-Control: no-cache\r\n"
                 "Accept-Ranges: none\r\n"
                 "Connection: close\r\n"
                 "\r\n", 
                 SOFTWARE, VERSION);
        block_inited = 1;
    }

    /* entity_t and body */
    rets = malloc(sizeof(struct entity_t));
    if (rets == NULL)
        return NULL;

    /* let all data as HTTP header */
    rets->header = block_buf;
    rets->header_length = size;
    rets->header_dyn = 0;
    rets->body = NULL;
    rets->body_length = 0;
    rets->body_dyn = 0;

    return rets;
}
